package lc20240522;

//求根节点到叶节点数字之和

import lc20240521.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

public class Demo2 {
    public static void main(String[] args) {

        TreeNode a = new TreeNode(2);
        TreeNode b = new TreeNode(3);
        b.left = new TreeNode(4);
        b.right= new TreeNode(5);
        TreeNode root = new TreeNode(1, a, b);
        System.out.println(sumNumbers(root));
    }

    //仍然是借用BFS的方法，借用两个队列。重要的是curSum的变化
    public static int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> sumQueue = new LinkedList<>();

        nodeQueue.add(root);
        sumQueue.add(root.val);
        int sum = 0;
        while (!nodeQueue.isEmpty()) {
            TreeNode curNode = nodeQueue.poll();
            int curSum = sumQueue.poll();
            if (curNode.left == null && curNode.right == null) {
                sum += curSum;
            }

            if (curNode.left != null) {
                nodeQueue.add(curNode.left);
                sumQueue.add(curSum * 10 + curNode.left.val);
            }
            if (curNode.right != null) {
                nodeQueue.add(curNode.right);
                sumQueue.add(curSum * 10 + curNode.right.val);
            }
        }
        return sum;
    }
}
